package com.zlk.algorithm.algorithm.dynamicPlan.threeDimension;

// 骑士在棋盘上的概率
// n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动
// 行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)
// 象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格
// 每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里
// 骑士继续移动，直到它走了 k 步或离开了棋盘
// 返回 骑士在棋盘停止移动后仍留在棋盘上的概率
// 测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/
public class Code03_KnightProbabilityInChessboard {

    public static void main(String[] args) {
        Code03_KnightProbabilityInChessboard test = new Code03_KnightProbabilityInChessboard();
        System.out.println(test.knightProbability(3, 2, 0, 0));
    }


    //    f1(n,i,j) ->  (i-2,j-1) (i-2,j+1) (i+2,j-1) (i+2,j+1)
    //                  (i-1,j-2) (i+1,j-2) (i+1,j+2) (i-1,j+2)
    //
    public double knightProbability(int n, int k, int row, int column) {
//        return f1(n,k,row,column);
//        double[][][] dp = new double[n][n][k + 1];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                for (int t = 0; t <= k; t++) {
//                    dp[i][j][t] = -1;
//                }
//            }
//        }
//        return f2(n,k,row,column,dp);
        return f3(n,k,row,column);
    }
    int[][] dirs = new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};
    //dp
    private double f3(int n, int k, int r, int c) {
        double[][] dp =new double[n][n];
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <n ; j++) {
                dp[i][j] = 1;
            }
        }
        for (int t = 1; t <k ; t++) {
            double[][] tempDp =dp;
            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <n ; j++) {
                    double ans = 0;
                    for (int[] d : dirs) {
                        int iIndex = i+d[0];
                        int jIndex = j+d[1];
                        if(iIndex<0||iIndex>=n||jIndex<0||jIndex>=n){
                            continue;
                        }
                        ans+=tempDp[iIndex][jIndex];
                    }
                    dp[i][j] = ans/8;
                }
            }
        }
        return dp[r][c];

    }

    private double f2(int n, int k, int row, int column,double[][][] dp) {
        if(row<0||row>=n||column<0||column>=n){
            return 0;
        }
        if (dp[row][column][k] != -1) {
            return dp[row][column][k];
        }
        if(k==0){
            dp[row][column][0]=1;
            return 1;
        }
        double ans = 0;
        ans = (f2(n,k-1,row-2,column-1,dp)+f2(n,k-1,row-2,column+1,dp)+
                f2(n,k-1,row+2,column-1,dp)+f2(n,k-1,row+2,column+1,dp)+
                f2(n,k-1,row-1,column-2,dp)+f2(n,k-1,row+1,column-2,dp)+
                f2(n,k-1,row+1,column+2,dp)+f2(n,k-1,row-1,column+2,dp))/8;
        dp[row][column][k] = ans;
        return ans;
    }

    private double f1(int n, int k, int row, int column) {
        if(row<0||row>=n||column<0||column>=n){
            return 0;
        }
        if(k==0){
            return 1;
        }
        return (f1(n,k-1,row-2,column-1)+f1(n,k-1,row-2,column+1)+
        f1(n,k-1,row+2,column-1)+f1(n,k-1,row+2,column+1)+
        f1(n,k-1,row-1,column-2)+f1(n,k-1,row+1,column-2)+
        f1(n,k-1,row+1,column+2)+f1(n,k-1,row-1,column+2))/8;
    }


}
